package com.buddy.learn.algorithm.simple;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 * 二叉树与数组：
 *  使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上，
 *  如果某一个节点的 Left 或者 Right 空缺，则数组的位置也会相应的空出来
 *
 *  parent 的 Left index = 2*parent+1 ；Right index=2*parent+2
 *  leftChild 的 parent = (leftChild -1)/2
 *
 * @author Buddy
 * @date 2021/4/20
 */
public class _二叉树 {

    private class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    private Node init() {
        // 必须逆序建立，因为上面的节点会用到下面的子节点
        Node N = new Node(7, null, null);
        Node H = new Node(6, null, null);
        Node E = new Node(5, H, N);
        Node D = new Node(4, null, null);
        Node C = new Node(3, null, null);
        Node B = new Node(2, D, E);
        Node A = new Node(1, B, C);
        return A;
    }

    private void printNode(Node root) {
        System.out.print(root.data + " ");
    }

    /**
     * 先序遍历：首先访问根结点然后遍历左子树，最后遍历右子树
     *
     * @param root 根节点
     */
    private void preOrder(Node root) {
        if (root != null) {
            printNode(root);
            if (root.left != null) {
                preOrder(root.left);
            }
            if (root.right != null) {
                preOrder(root.right);
            }
        }
    }

    /**
     * 先序遍历，不使用递归
     *
     * @param root 根节点
     */
    private void preOrder2(Node root) {
        // 栈，先进后出
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                // 打印当前节点
                printNode(root);
                // 如果root 不为空，先放到栈里，用于后面获取右子树
                stack.push(root);
                // root 设定为左子树
                root = root.left;
            }
            if (!stack.empty()) {
                // 弹出最后一个节点
                root = stack.pop();
                // root 设定为右子树
                root = root.right;
            }
        }
    }

    /**
     * 中序遍历，首先遍历左子树，然后访问根结点，最后遍历右子树。
     *
     * @param root 根节点
     */
    private void middleOrder(Node root) {
        if (root != null) {
            middleOrder(root.left);
            printNode(root);
            middleOrder(root.right);
        }
    }

    /**
     * 中序遍历，不使用递归
     *
     * @param root 根节点
     */
    private void middleOrder2(Node root) {
        // stack 先进后出
        Stack<Node> stack = new Stack<>();
        // 如果根节点不为空，或者 stack 中有数据
        while (root != null || !stack.empty()) {
            while (root != null) {
                // 如果 root 不为空
                stack.push(root);
                root = root.left;
            }
            if (!stack.empty()) {
                // 如果 stack 中有数据
                root = stack.pop();
                printNode(root);
                root = root.right;
            }
        }
    }

    /**
     * 后序遍历
     *
     * @param root 根节点
     */
    private void afterOrder(Node root) {
        if (root != null) {
            afterOrder(root.left);
            afterOrder(root.right);
            printNode(root);
        }

    }

    /**
     * 后续遍历不使用递归
     *
     * @param root 根节点
     */
    private void afterOrder2(Node root) {
        Stack<Node> stack = new Stack<>();
        Stack<Node> output = new Stack<>();
        while (root != null || !stack.empty()) {
            if (root != null) {
                stack.push(root);
                output.push(root);
                root = root.right;
            } else {
                root = stack.pop();
                root = root.left;
            }
        }
        while (!output.empty()) {
            printNode(output.pop());
        }
    }

    /**
     * 层次遍历
     * 层次遍历使用到了广度优先搜索，技巧：深度优先用递归，广度优先用队列
     *
     * @param root
     */
    private void levelOrder(Node root) {
        // 队列，先进先出 FIFO
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 跟节点出队列
            root = queue.poll();

            printNode(root);
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
        }

    }

    private int treeMaxDeep(Node root) {
        // 如果当前二叉树节点为空，则直接返回 0；
        if (root == null) {
            return 0;
        }
        // 通过递归调用，分别获取当前节点左右子树的最大深度；
        int ld = treeMaxDeep(root.left);
        int rd = treeMaxDeep(root.right);
        // 左右子树最大深度的较大值加1，即二叉树的最大深度。
        return ld > rd ? ld + 1 : rd + 1;
    }

    private int treeMinDeep(Node root) {
        //1. 如果当前二叉树节点为空，则直接返回 0；
        if (root == null) {
            return 0;
        }

        //2. 通过递归调用，分别获取当前节点左右子树的最小深度；
        int lMinD = treeMinDeep(root.left);
        int rMinD = treeMinDeep(root.right);

        //3. 如果当前节点的左子树为空，则其最小深度就是右子树最小深度加 1；
        if (null == root.left) {
            return rMinD + 1;
        }
        //4. 如果当前节点的右子树为空，则其最小深度就是左子树最小深度加 1；
        if (null == root.right) {
            return lMinD + 1;
        }
        //5. 如果左右子树都不为空，则其最小深度为左右子树最小深度的较小值加 1；
        return lMinD < rMinD ? lMinD + 1 : rMinD + 1;
    }

    private int treeWidth(Node root) {
        if (root == null){
            return 0;
        }
        // 广度优先用队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int maxWidth = 1;
        while (!queue.isEmpty()){
            // 当前层的数据，当前层的宽度
            int len = queue.size();
            while (len-- > 0){
                // 如果当前层还有节点
                root = queue.poll();
                // 下层有数据，入队
                if (root.left != null){
                    queue.add(root.left);
                }
                if (root.right != null){
                    queue.add(root.right);
                }
            }
            maxWidth = maxWidth > queue.size() ? maxWidth : queue.size();
        }
        return maxWidth;
    }


    public static void main(String[] args) {
        _二叉树 binaryTree = new _二叉树();
        Node root = binaryTree.init();

        System.out.println(">>> 先序遍历：");
        binaryTree.preOrder(root);
        System.out.println();
        System.out.println(">>> 先序遍历，不使用递归：");
        binaryTree.preOrder2(root);
        System.out.println();

        System.out.println(">>> 中序遍历：");
        binaryTree.middleOrder(root);
        System.out.println();
        System.out.println(">>> 中序遍历，不使用递归：");
        binaryTree.middleOrder2(root);
        System.out.println();


        System.out.println(">>> 后序遍历：");
        binaryTree.afterOrder(root);
        System.out.println();
        System.out.println(">>> 后序遍历，不使用递归：");
        binaryTree.afterOrder2(root);
        System.out.println();


        System.out.println(">>> 层次遍历：");
        binaryTree.levelOrder(root);
        System.out.println();


        System.out.println(">>> 树的最大深度：" + binaryTree.treeMaxDeep(root));
        System.out.println(">>> 树的最小深度：" + binaryTree.treeMinDeep(root));
        System.out.println(">>> 树的宽度：" + binaryTree.treeWidth(root));
    }




}
